home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-01 / snip0493.zip / PERMUTE1.C < prev    next >
C/C++ Source or Header  |  1993-04-05  |  4KB  |  115 lines
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3.  
  4. /*  chouse_n ( char *strng, int length) returns a pointer to a string of   */
  5. /*  length characters chosen from "strng" , duplicate chars in "strng" are */
  6. /*  significant.  Strings are generated in lexical order.                  */
  7. /*  First call, call with *strng. each subsiquent call, call with NULL,    */
  8. /*  returns one combination. Calls after all combinations have been        */
  9. /*  returned return NULL.  Will return NULL for errors.                    */
  10. /*  not very defensive (i.e. WILL BREAK)                                   */
  11.  
  12. /*  dave chapman aug '91  released to public domain                        */
  13.  
  14. char *chouse_n( char *strng, int length);
  15.  
  16. char *chouse_n( char *strng, int length)
  17. {
  18.       static char *str;
  19.       static char *curr;
  20.       static char *pos;       /* for each char in curr(ent string),
  21.                                  its pos in str                            */
  22.       static int  counts[256];
  23.       int i,j;
  24.  
  25.       if (0 >= length)
  26.             return NULL;
  27.  
  28.       if (NULL != strng)
  29.       {
  30.             str = malloc(strlen(strng)); /* first call, prep string for use */
  31.             curr = malloc(2 * length + 1);
  32.             pos = curr + length +1;
  33.  
  34.             for (i = 0; i < 256; counts[i++] = 0)
  35.                   ;
  36.             for (i = 0; strng[i]; i++)
  37.                   counts[strng[i]]++;
  38.  
  39.             for (i = 1, j = 0; i < 256; i++)
  40.             {
  41.                   if (counts[i])
  42.                   {
  43.                         str[j] = i;
  44.                         counts[j++] = counts[i];
  45.                   }
  46.             }
  47.             str[j] = '\0';      /* str is string of distinct chars in order */
  48.                                 /* counts[] holds count of each char        */
  49.  
  50.             /* take first length chars */
  51.  
  52.             for (i = 0,j = 0; i < length; i++)
  53.             {
  54.                   curr[i] = str[j];
  55.                   pos[i] = j;
  56.                   if (!(--counts[j]))
  57.                         j++;
  58.             }
  59.             curr[i] = '\0';
  60.             return curr;
  61.       }
  62.       /* if called with "mississippi",5;
  63.          str -> "imps"
  64.          curr -> "iiiim"
  65.          counts -> 0,0,2,4;
  66.          pos -> 0,0,0,0,1;   */
  67.       
  68.       /* go back to front */
  69.  
  70.       for (j = length; j > 0;)
  71.       {
  72.             counts[ pos[--j]]++;                      /* "replace" char */
  73.  
  74.             /* look for a new char for curr posit. */
  75.  
  76.             for ( i = ++pos[j]; str[i] && ! counts[i]; i++)
  77.             ;
  78.             if (0 != (curr[j] = str[i]))              /* found a char   */
  79.             {
  80.                   --counts[i];
  81.                   pos[j] = i;
  82.  
  83.                   /* placed char, fill out rest of string  */
  84.  
  85.                   for (++j, i = 0; j < length; j++)
  86.                   {
  87.                         for ( ; !counts[i]; i++)
  88.                               ;
  89.                         curr[j] = str[i];       /* first available char */
  90.                         --counts[i];
  91.                         pos[j] = i;
  92.                   }
  93.                   return curr;
  94.             }
  95.             /* no more chars for this pos ; go back one */
  96.       }
  97.       /*  done */
  98.       return NULL;
  99. }
  100.  
  101. void main(void)
  102. {
  103.       char  *str = "aabbccdd";
  104.       int i,j;
  105.  
  106.       j = 0;
  107.       i =  5;
  108.       puts(chouse_n( str, i));
  109.       while (NULL != (str = chouse_n(NULL, i)))
  110.       {
  111.             ++j;
  112.             printf(" %s  %d\n",str,j);
  113.       }
  114. }
  115.